/**
 * //You are given an integer array coins representing coins of different
 * //denominations and an integer amount representing a total amount of money.
 * //
 * // Return the fewest number of coins that you need to make up that amount. If
 * //that amount of money cannot be made up by any combination of the coins, return -1.
 * //
 * //
 * // You may assume that you have an infinite number of each kind of coin.
 * //
 * //
 * // Example 1:
 * //
 * //
 * //Input: coins = [1,2,5], amount = 11
 * //Output: 3
 * //Explanation: 11 = 5 + 5 + 1
 * //
 * //
 * // Example 2:
 * //
 * //
 * //Input: coins = [2], amount = 3
 * //Output: -1
 * //
 * //
 * // Example 3:
 * //
 * //
 * //Input: coins = [1], amount = 0
 * //Output: 0
 * //
 * //
 * //
 * // Constraints:
 * //
 * //
 * // 1 <= coins.length <= 12
 * // 1 <= coins[i] <= 2³¹ - 1
 * // 0 <= amount <= 10⁴
 * //
 * //
 * // Related Topics 广度优先搜索 数组 动态规划 👍 2075 👎 0
 */

package com.xixi.basicAlgroithms.dynamicPrograming;

import java.util.Arrays;

public class ID00322CoinChange {
    public static void main(String[] args) {

        Solution solution = new ID00322CoinChange().new Solution();
        System.out.println(solution.coinChange(new int[]{431, 62, 88, 428}, 9084));
    }


    //leetcode submit region begin(Prohibit modification and deletion)
    class Solution {
        public int coinChange(int[] coins, int amount) {
            if (amount == 0) return 0;

            //sort，从大到小
            Arrays.sort(coins);
            int i = coins.length - 1;
            while (i >= 0) {
                if (coins[i] == amount) {
                    return 1; //如果有等于的，一个面值就够了
                }
                if (coins[i] < amount) { //从小于amount的最大面值开始，可以减少使用coin的个数
                    break;
                }
                --i;

            }

            int largestUseableCoinsIndex = i; //记录最大可用面值的index


            //动态规划, 记录到达该面值需要的最小coin数
            int[] status = new int[amount + 1];

            //初始化status,每个面值的硬币放一枚
            while (i >= 0) {
                status[coins[i]] = 1;
                i--;
            }

            //动态规划

            for (i = largestUseableCoinsIndex; i >= 0; --i) {
                int coinValue = coins[i];
                for (int j = 1; j + coinValue <= amount; ++j) {
                    int jStat = status[j];
                    if (jStat == 0) {
                        continue;//还未能出现到达该value的情况
                    } else {//之前的coin能达到此状态
                        int nextValue = j + coinValue;
                        int nextValueStat = status[nextValue];
                        if (nextValueStat == 0) {
                            status[nextValue] = jStat + 1;
                        } else {
                            status[nextValue] = Math.min(nextValueStat, jStat + 1); //取最小面值数
                        }

//                    if((nextValue) == amount) return jStat + 1; //这里不能直接返回，否则有可能会出现返回的不是最少coin数目的情况

                    }
                }
            }


            return status[amount] == 0 ? -1 : status[amount];


        }
    }
//leetcode submit region end(Prohibit modification and deletion)


}